package demo21;

/*
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class Test {
    public static void main(String[] args) {

        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        ListNode result = mergeTwoLists(l1,l2);
        while(result != null){
            System.out.print(result.val+" ");
            result = result.next;
        }

    }


    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //判断是否其中一个链表或者两个链表都为空
        if(l1 == null){
            return l2;
        }else if(l2 == null){
            return l1;
        }
        //比较两个链表当前值，小的那个作为新链表的起点
        ListNode ln;
        if(l1.val < l2.val){
            ln = l1;
            l1 = l1.next;
        }else{
            ln = l2;
            l2 = l2.next;
        }
        ListNode result = ln;//保存起点，最后用来返回结果
        //开始循环读取
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                //l1当前节点小
                ln.next = l1;
                ln = ln.next;
                l1 = l1.next;
            }else{
                //l2当前节点小
                ln.next = l2;
                ln = ln.next;
                l2 = l2.next;
            }
        }
        //判断是否有其中一个链表有剩余
        if(l1 == null){
            ln.next = l2;
        }else{
            ln.next = l1;
        }
        return result;
    }

}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}